package com.cqut.forum.util;

/**
 * 快速排序公共类
 * @author yangxun
 */
public abstract class MyQuickSort {
	public static void quickSort(int[] src){
		sort(0,src.length-1,src);
	}
	private static void sort(int s,int e,int[] src){
		if(s >= e){
			return;
		}
		int target = src[s];
		int i,j;
		for(i =s+1,j =e;i<e&&i<j;){
			int left = src[i];
			int right = src[j];
			
			while(left<target){
				left = src[++i];
				if(i>=j){
					left = src[++i];
					break;
				}
			}
			while(right>=target){
				right = src[--j];
				if(j<=i){
					break;
				}
			}			
			int m = left;
			src[i]=src[j];
			src[j]=m;
		}
		src[s] = src[i-1];
		src[i-1] = target;
		for(int d:src){
			System.out.print(d+" ");
		}
		System.out.println();
		sort(s,i-1,src);
		sort(i+1,e,src);
	}
	
}
